The present invention relates to an information transfer device and method, an information receiving device and method and network stations using them.
8-state amplitude modulation (known by the name xe2x80x9c8-AMxe2x80x9d) can be described as follows. In order to transmit information, an alphabet
A={xe2x88x927, xe2x88x925,xe2x88x923,xe2x88x921,1,3,5,7}
containing eight numbers, referred to as elementary signals, is available. At each instant r.T, with r=0, 1, 2, . . . , a multiple of an elementary duration T, an information source selects a number a from the alphabet A and transmits this number a to a modulator. This modulator produces, between the instants r.T and (r+1).T, the electrical signal a. cos(2.xcfx80.f.t) (or, more precisely, a signal of amplitude proportional to a. cos(2.xcfx80.f.t)), where t is the time and f is the frequency of the carrier.
A received signal is often modified, for example by noise. This means that the received signal corresponding to a transmitted signal a. cos(2.xcfx80.f.t) (a being in the alphabet A) will be measured and evaluated as corresponding to the transmission of b. cos(2.xcfx80.f.t), a formula in which b may be different from a and is moreover not necessarily an element of A.
Sometimes, the noise level or modification, during a period T, are sufficiently high to make b. cos(2.xcfx80.f.t) closer to a*. cos(2.xcfx80.f.t) with a* in A, and a* different from a, than to any other transmittable signal, including a. cos(2.xcfx80.f.t). In this case, the decision rule is to estimate that a* was transmitted and an estimation error appears. It can be demonstrated that, with Additive White Gaussian Noise conditions, the probability of such an estimation error depends greatly on the amount (a-a*)2.T, and, the smaller the said amount, the higher this probability will be.
In particular, the probability of estimating a*=xe2x88x927 when a=7 was transmitted is very low and the probability of estimating a*=3 when a=1 was transmitted is higher.
Furthermore, it is wished to have easy access to the information while receiving the noisy message. This property is referred to as an easy decoding method.
These same reasonings are found again for other amplitude modulation methods, such as 16-AM modulation (16-state amplitude modulation), for quadrature amplitude modulation methods, such as 64-QAM modulation (64-state quadrature amplitude modulation) and for phase modulation methods such as 8-PSK modulation (8-state phase modulation).
Let, for example, information transmission by means of 8-state amplitude modulated (xe2x80x9c8-AMxe2x80x9d) signals or 64-state quadrature amplitude modulated (xe2x80x9c64-QAMxe2x80x9d) signals be considered.
In the case of 8-AM modulation, the eight possible signals are therefore eight amplitudes proportional to the eight numbers of the alphabet A={xe2x88x927, xe2x88x925, xe2x88x923, xe2x88x921, 1, 3, 5, 7}, and in the case of 64-QAM modulation, the sixty-four possible signals are the sixty-four amplitude pairs (a, b), where a and b are two amplitudes each being proportional to one of the eight numbers of the alphabet A. A sequence of length n in the 64-QAM modulation alphabet can therefore be viewed as a sequence of length 2n in the 8-AM alphabet and everything which is said concerning coding adapted to 8-AM modulation can therefore easily be adapted to 64-QAM modulation.
When these signals are transmitted on a channel, for example a channel with Additive White Gaussian Noise (xe2x80x9cAWGNxe2x80x9d), the probability that the received signal is estimated as being equal to a2 when the signal sent is a1 depends, in effect, on the actual values of a1 and a2.
Many methods used in practice do not, however, take these probabilities into account. These are designed to correct a certain number of erroneous received symbols, but their corrective capability is not expressed in terms of total amplitude of the error. In other words, they take into account only the Hamming distance between the received word and the code words, to the detriment of any other distance measurement, like for example the Lee distance.
Of course, efforts are sometimes made to take into account the amplitude of the error in the decoder but most often in the case of soft decoding, which makes the decoding expensive, or in the case of a channel whose input alphabet has at most four letters. On this subject, the article by Hammons, Kumar, Calderbank, Sloane and Solxc3xa9 entitled xe2x80x9cThe Z4- linearity of Kerdock, Preparata, Goethals and related codesxe2x80x9d, IEEE Trans. On Inform. Theory, IT-40, pages 301 to 319, published in March 1994, should be consulted.
The present invention is concerned with a method of algebraic decoding of certain codes in the alphabet A, based on a judicious labelling of the elements of this alphabet by the integers 0, 1, . . . , 7, using a hard estimation of the received symbols and a notion of distance between words which is close to the Lee distance. On the subject of Hamming and Lee distances, the book by E. Berlekamp xe2x80x9cAlgebraic Coding Theoryxe2x80x9d published by McGraw-Hill in 1968 should be consulted. Simultaneously, specific coding schemes which produce good codes which can be decoded by this method will be described.
The invention aims to propose a coding method and device and, correlatively, a decoding method and device, which make it possible to recover the transmitted information, in the presence of noise.
An alphabet will be referred to as xe2x80x9cnumericalxe2x80x9d if its symbols are real numbers or complex numbers viewed as pairs of real numbers. In an alphabet of real numbers, two symbols will be referred to as xe2x80x9cadjacentxe2x80x9d if the alphabet does not contain any other number which is both greater than one of these numbers and less than the other.
To this end, the present invention relates, according to a first aspect, to an information transfer method, characterised in that:
it uses:
an alphabet Z2t={0, 1, 2, . . . 2txe2x88x921} having 2t elements, where t is at least equal to 3, and in which additions and multiplications are carried out modulo 2t, and
a cyclic code, possibly abbreviated, referred to as a xe2x80x9clifted Hamming codexe2x80x9d obtained by lifting a binary Hamming code, and whose generator polynomial is the lifting into Z2t of a generator polynomial of odd degree in {0, 1} of such a binary Hamming code; and
it includes:
an operation of coding the information by a sequence of words of the said lifted Hamming code,
a labelling operation, during which each letter of the alphabet Z2t is used to label a letter of a numerical alphabet A, so that, for any pair of so-called xe2x80x9cadjacentxe2x80x9d symbols of A, the label of one of these symbols is the residue modulo 2t of the label of the other incremented by 1,
for each word of the said lifted Hamming code, an operation of transmitting signals with amplitudes proportional to the elements of A labelled by each of the symbols of the words of the said lifted Hamming code.
A labelling of the alphabet A satisfying the conditions described above (for any pair of so-called xe2x80x9cadjacentxe2x80x9d symbols of A, the label of one of these symbols is the residue modulo 2t of the label of the other incremented by 1) is referred to as xe2x80x9cfavourablexe2x80x9d. A favourable labelling of a numerical alphabet is easily achieved by applying a principle of consecutiveness, of which here is an application:
Correlatively, according to a second aspect, the present invention relates to a method of receiving a sequence of physical quantities representing information, characterised in that:
it uses:
a numerical alphabet A,
an alphabet Z2t={0, 1, 2, . . . 2txe2x88x921} having 2t elements, where t is at least equal to 3, and in which additions and multiplications are carried out modulo 2t, and
a cyclic code, possibly abbreviated, referred to as a xe2x80x9clifted Hamming codexe2x80x9d obtained by lifting a binary Hamming code, and whose generator polynomial is the lifting into Z2t of a generator polynomial of odd degree in {0, 1} of such a binary Hamming code; and
it includes:
an operation of demodulating each received signal into a letter of the alphabet A,
a labelling operation, during which each letter of the alphabet Z2t is used to label a letter of the numerical alphabet A, so that, for any pair of so-called xe2x80x9cadjacentxe2x80x9d symbols of A, the label of one of these symbols is the residue modulo 2t of the label of the other incremented by 1,
an operation of decoding each sequence of labels, into a sequence of the said lifted Hamming code.
In fact, the inventor has discovered that, for any value of t at least equal to 3, the Lee distance between two different sequences of such a lifted Hamming code is always equal to or greater than 5. Therefore, by virtue of the present invention, at least the errors whose Lee weight is equal to 1 or 2 can be corrected.
According to particular characteristics, the decoding operation includes an error correction operation which includes:
an operation of verifying that the syndrome is compatible with an error affecting only one element of the sequence of labels,
in the negative case, an operation of determining couples of positions of erroneous elements compatible with the syndrome, couples the number of which is at most equal to half the length of the lifted Hamming code.
By virtue of these provisions, the number of couples of positions to be considered is greatly reduced.
According to particular characteristics, the decoding operation includes an operation of determining at least one reduced syndrome, the m-tuple s(q) equal to the column m-tuple s=HrT referred to as the xe2x80x9csyndromexe2x80x9d and reduced modulo the positive integer number q equal to a power of 2, where H is the control matrix of the lifted Hamming code used.
The consideration of these reduced syndromes facilitates the decoding.
According to particular characteristics, in the information receiving method as briefly described above:
as a preliminary to the decoding operation, an operation is performed of calculating the residue modulo 8, of each element of the syndrome s equal to the product HrT, modulo 2t, where H is the control matrix of the lifted Hamming code used and
the decoding operation includes the determination of each position of a possibly erroneous element, using the said residue.
By virtue of these provisions, the invention is easily applied to any modulation of the 2t-AM or 22t-QAM type, with t equal to or greater than 4.
According to a third aspect, the present invention relates to an information transfer device, characterised in that it has:
A/ a processing means adapted:
to use:
an alphabet Z2t={0, 1, 2, . . . 2txe2x88x921} having 2t elements, where t is at least equal to 3, and in which additions and multiplications are carried out modulo 2t, and
a cyclic code, possibly abbreviated, referred to as a xe2x80x9clifted Hamming codexe2x80x9d obtained by lifting a binary Hamming code, and whose generator polynomial is the lifting into Z2t of a generator polynomial of odd degree in {0, 1} of such a binary Hamming code; and
to code the information by a sequence of words of the said lifted Hamming code,
to label each letter of the alphabet A by a letter of the alphabet Z2t, so that, for any pair of so-called xe2x80x9cadjacentxe2x80x9d symbols of A, the label of one of these symbols is the residue modulo 2t of the label of the other incremented by 1, and
B/ a transmission means adapted, for each word of the said lifted Hamming code, to transmit signals, a physical quantity of which is proportional to the elements of A labelled by each of the symbols of the words of the said lifted Hamming code.
According to a fourth aspect, the present invention relates to an information receiving device, characterised in that it has:
A/ a signal receiving means adapted to demodulate each received signal in order to produce at least one letter of the alphabet A,
B/ a processing means adapted:
to use:
a numerical alphabet A,
an alphabet Z2t={0, 1, 2, . . . 2txe2x88x921} having 2t elements, where t is at least equal to 3, and in which additions and multiplications are carried out modulo 2t, and
a cyclic code, possibly abbreviated, referred to as a xe2x80x9clifted Hamming codexe2x80x9d obtained by lifting a binary Hamming code, and whose generator polynomial is the lifting into Z2t of a generator polynomial of odd degree in {0, 1} of such a binary Hamming code; and
to label each letter of the numerical alphabet A by a letter of the alphabet Z2t, so that, for any pair of so-called xe2x80x9cadjacentxe2x80x9d symbols of A, the label of one of these symbols is the residue modulo 2t of the label of the other incremented by 1,
to decode each sequence of labels v, into a sequence r of the said lifted Hamming code.
The invention also relates to:
an information storage means readable by a computer or a microprocessor storing instructions of a computer program, characterised in that it allows the implementation of the method of the invention as briefly described above, and
an information storage means which is removable, partially or totally, and readable by a computer or a microprocessor storing instructions of a computer program, characterised in that it allows the implementation of the method of the invention as briefly described above.
The invention also relates to a network station, which has an information transfer device as briefly described above.
The invention also relates to a network station, which has an information receiving device as briefly described above.
Since this information transfer device, this information receiving device, these storage means and these network stations have the same particular characteristics and the same advantages as the information transfer method briefly described above, these particular characteristics and these advantages are not repeated here.